package DataStructure.graph;

import java.util.ArrayDeque;
import java.util.Deque;

//无向无权图
public class Graph {
    private int V;//顶点数量
    private int E;//边数量
    private Deque<Edge> edge;//边
    private int[] degree;//顶点的度
    private Deque<Integer>[] adj;//邻接表
    private boolean[] mark;//访问标志


    public Graph(int v){
        V=v;
        E=0;
        edge=new ArrayDeque<>();
        degree=new int[v];
        adj=new ArrayDeque[v];
        for (int i = 0; i < adj.length; i++) {
            adj[i]=new ArrayDeque<>();
        }
        mark=new boolean[v];
    }

    //与v相邻的所有顶点
    public Deque<Integer> near(int v){
        return adj[v];
    }

    //添加一条边
    public void addEdge(int v,int w){
        if(adj[v].contains(w))
            return;
        edge.add(new Edge(v,w));
        degree[v]++;
        degree[w]++;
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }


    //深度优先搜索 test
    //递归
    public void dfs(int v){
        mark[v]=true;
        for (int w : adj[v]) {
            if(!mark[w])
                dfs(w);
        }
    }
    //非递归
    public void dfs2(int v){
        Deque<Integer> s=new ArrayDeque<>();
        s.offer(v);
        while (!s.isEmpty()){
            int cur=s.pollLast();//从最后进入的开始遍历
            for (int w : adj[cur]) {
                if(!mark[w]){
                    s.offer(w);
                    mark[w]=true;
                }
            }
        }
    }
    //广度优先搜索
    //非递归
    public void bfs2(int v){
        Deque<Integer> q=new ArrayDeque<>();
        q.offer(v);//起点入队
        mark[v]=true;
        while (!q.isEmpty()){
            int cur=q.poll();//从先进入的开始遍历
            //后面节点入队
            for (int w : adj[cur]) {
                if(!mark[w]){
                    q.offer(w);
                    mark[w]=true;
                }
            }
        }
    }
    //按层非递归
    public void bfs2ByLayer(int v){
        int layer=0;//当前层
        Deque<Integer> q=new ArrayDeque<>();
        q.offer(v);//起点入队
        mark[v]=true;
        while (!q.isEmpty()){
            int n=q.size();//当前层数量
            for (int i = 0; i < n; i++) {
                int cur=q.poll();//从先进入的开始遍历
                //下一层入队
                for (int w : adj[cur]) {
                    if(!mark[w]){
                        q.offer(w);
                        mark[w]=true;
                    }
                }
            }
            layer++;
        }
    }
    //递归
    public void bfs(Deque<Integer> q){
        if(q.isEmpty()) return;
        int cur=q.poll();
        for (int w : adj[cur]) {
            if(!mark[w]){
                q.offer(w);
                mark[w]=true;
            }
        }
        bfs(q);
    }
    //按层递归
    public void bfsByLayer(Deque<Integer> q,int layer){
        if(q.isEmpty()) return;
        int n=q.size();
        for (int i = 0; i < n; i++) {
            int cur=q.poll();
            for (int w : adj[cur]) {
                if(!mark[w]){
                    q.offer(w);
                    mark[w]=true;
                }
            }
        }
        bfsByLayer(q,layer+1);
    }

    //A*搜索
    public void AStar(){

    }

}
